package pers.qianyu.month_202102.date_20210217;

import java.util.*;

/**
 * 867. 四键键盘
 * https://www.lintcode.com/problem/867/
 * - 超时（58% 数据通过测试）
 *
 * @author mizzle rain
 * @date 2021-02-17 11:56
 */
public class MaxA {
    Map<Node, Integer> memo = new HashMap<>();

    public int maxA(int N) {
        if (N == 0) return 0;
        return dp(N, 0, 0);
    }

    int dp(int n, int a, int copy) {
        if (n <= 0) return a;
        Node node = new Node(n, a, copy);
        if (memo.containsKey(node)) return memo.get(node);
        int res = Math.max(dp(n - 1, a + 1, copy),
                Math.max(dp(n - 1, a + copy, copy), dp(n - 2, a, a)));
        memo.put(node, res);
        return res;
    }

    static class Node {
        int n;
        int a;
        int copy;

        public Node(int n, int a, int copy) {
            this.n = n;
            this.a = a;
            this.copy = copy;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Node node = (Node) o;

            if (n != node.n) return false;
            if (a != node.a) return false;
            return copy == node.copy;
        }

        @Override
        public int hashCode() {
            int result = n;
            result = 31 * result + a;
            result = 31 * result + copy;
            return result;
        }
    }
}
